package com.demo.jzoffer2;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0317_01 {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    /**
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，
     * 还有一个 random 指针指向链表中的任意节点或者 null。
     *
     * 思路分析：给定链表的头节点 head，复制普通链表很简单，只需要遍历链表，每轮建立新节点+构建前驱节点 pre
     * 和当前节点 node 的引用指向即可
     *
     * 本题中链表的节点新增了 random 指针，指向链表中的 *任意* 节点 或者 null 这个random指针意味着在复制的过程中，
     * 处理需要构建  1、前驱节点 和 当前节点的引用指向 pre.next  Node next;
     * 2、还需构建前驱节点 和 随机节点的引用指向 pre.random  Node random;
     *
     * 难点：在复制链表的过程中构建新链表个节点的 random 的引用指向
     *
     * 方法：哈希表
     * 考虑到构建原链表节点 和 新链表对应节点的键值对银蛇关系，再遍历构建新链表各节点的 next 和 random 引用指向即可
     *
     * 算法流程：
     * 1.若头节点为空系欸但，直接返回 null
     * 2.初始化： 哈希表 dic 节点cur 指向头节点
     * 3.复制链表
     * a.建立新节点，并向dic添加键值对 （原cur节点 新cur节点）
     * b.cur 遍历至原链表的下一节点
     * 4.构建新链表的引用指向
     * a.构建新节点 next 和 random 引用指向
     * b.cur 遍历至原链表的下一节点
     *
     * 复杂度分析：时间 O（N） 两轮遍历链表 使用 O（N）
     * 空间：哈希表 dic 使用线性大小的额外空间
     * @param head
     * @return
     */
    public Node copyRandomList2(Node head) {
        Node cur = head; // 当前节点
        Node dum = new Node(0),pre = dum; // 前驱节点
        while (cur != null){
            Node newNode = new Node(cur.val); // 复制节点
            pre.next = newNode; // 新链表的 前驱节点 -> 当前节点
//            pre.random = ???; // 新链表的 [前驱节点-> 当前节点] 无法确定
            cur = cur.next; // 遍历至下一节点
            pre = newNode; // 保存当前新节点
        }
        return dum.next;
    }

    public Node copyRandomList(Node head) {
        // 1. 若头节点为空，直接返回 null
        if (head == null){
            return null;
        }
        // 2.初始化： 哈希表 dic 节点cur 指向头节点
        HashMap<Node, Node> dic = new HashMap<>();
        Node cur = head;
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while (cur != null) {
            dic.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        // 注意：此处要初始化当前节点为 头节点
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while (cur != null) {
            // 新链表的 next      为 cur.next
            dic.get(cur).next = dic.get(cur.next);
            // 新链表的 random    为 cur.random
            dic.get(cur).random = dic.get(cur.random);
            cur = cur.next;
        }

        // 5. 返回新链表的头节点
        return dic.get(head);
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3(){

    }

}
